ass Solution {
public:
    int search(vector<int>& nums, int target) {
        // 1  2  4  5  7  9 
        int left =0; int right = nums.size()-1;
        while(left<=right)
        {
            int mid = (left+right)/2;
            if(nums[mid]>target)
            {
                right=mid-1;
            }
            else if(nums[mid]<target)
            {
                left = mid+1;
            }
            else
            {
                return mid;
            }
        }
        return -1;
    }
};

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        // 1 1 3 5 4 3 3 7   3
        int cur=0;
        int next=0;

        while(next<nums.size())
        {
            if(nums[next] != val)
            {
                nums[cur++]=nums[next];               
            }
            next++;
        }
        return cur;
    }
}

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        vector<int> ret;
        for(auto e:nums)
        {
            ret.push_back(e*e);
        }
        sort(ret.begin(),ret.end());
        return ret;
    }
};

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        vector<int> ret(nums.size());
        int left=0;
        int right=nums.size()-1;

        int i=nums.size()-1;
        while(left<=right)
        {
            if(nums[left]*nums[left]<nums[right]*nums[right])
            {
                ret[i--]=nums[right]*nums[right];
                right--;
            }
            else
            {
                ret[i--]=nums[left]*nums[left];
                left++;
            }
        }
        return ret;
    }
};
